public class Solution53 {
    public int maxSubArray(int[] nums) {
        int[] preSum = new int[nums.length - 1];
        preSum[0] = 0;
        int maxSum = Integer.MIN_VALUE;
        int minPreSum = 0;
        for(int i = 1;i < nums.length + 1;i++){
            preSum[i] = preSum[i-1] + nums[i-1];
            maxSum = Math.max(maxSum,preSum[i] - minPreSum);
            minPreSum = Math.min(minPreSum,preSum[i]);
        }
        return maxSum;
    }
}
